import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean[] st;
    public List<List<Integer>> res = new ArrayList<>();

    public void dfs(int n, int u, int idx, int k) {
        if (u == k) {
            List<Integer> list = new ArrayList<>();
            for (int i = 1; i <= n; i++) {
                if (st[i]) {
                    list.add(i);
                }
            }
            res.add(list);
            return;
        }

        for (int i = idx; i <= n; i++, idx++) {
            if (!st[i]) {
                st[i] = true;
                dfs(n, u + 1, idx + 1,k);
                st[i] = false;
            }
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        st = new boolean[n + 1];
        dfs(n, 0, 1, k);
        return res;
    }
}